1. Field of Invention
This invention relates in general to data caches, and more particularly, to data structure reordering.
2. Description of Background
Data cache efficiency is a major performance bottleneck in modern computer systems. Extensive research effort has been dedicated to the improvement of data cache utilization on data layout transformation, typically array padding and array data structure reordering are utilized to exploit data reuse. These optimizations are particularly effective in the domain of scientific computing in which programs operate extensively on arrays.
Nowadays, many applications also make extensive use of pointers to store data using low-level programming languages that support pointers, such as C and C++. The pointer-intensive programs are a difficult challenge for modern computer architectures and memory hierarchies. Typical pointer-based heap allocated data tends to have less regular access pattern with much worse reference locality than an array. An effective way to overcome this drawback is to allocate data in a manner to increase the programs' reference locality.
The recent work provides a practical, safe, and automatic data reshaping and data merging framework that reorganizes dynamic arrays of objects to improve data locality. Two major approaches have been described for reorganizing these data structures: Arithmetic-based reshaping relies on a mathematical formula to map object components from their original location to their remapped location. Pointer-based reshaping introduces pointers inside the original data structure to indicate where some components have been relocated.
It has been shown that arithmetic-based reshaping always performs better than the pointer-based reshaping, as it requires no additional components to be introduced and maintained inside the structure. Yet, so far arithmetic-based reshaping has been restricted to single-instantiation cases to avoid unsafe code transformations. The single-instantiation restriction says that there must be a single allocation point for a particular object type, and that this point must be executed no more than once at run time so that the base address of the object is a constant at runtime. However, many programs operate on data structures that are typically not allocated monolithically into a dynamic object. Even in cases where there is effectively a single instantiation at runtime, it may be difficult or even impossible for a compiler to statically prove that the call site will only be executed no more than once. The challenge to handle individually allocated objects imposes the difficult task upon a user to analyze all the dynamically placed objects involved in a data structure at compile time and to do a safe code transformation.
Thus, there is a need for a method that provides a novel and efficient method for dynamically allocated data reshaping with multiple object instantiations.